/*
solution of https://www.luogu.com.cn/problem/T637677
*/

#include <cstdint>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

using ll = int64_t;

const ll f = 50000;
const ll msize = 100001;
const ll inf = 1000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n, m;
    cin >> n >> m;
    vector<ll> d(n);
    long long T0 = 0;
    for (ll i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        d[i] = a - b;
        T0 += d[i];
    }

    vector<ll> dp0(msize, inf);
    vector<ll> dp1(msize, inf);

    if (0 + f >= 0 && 0 + f < msize) {
        dp0[0 + f] = 0;
    }
    ll nx0 = d[0] + f;
    if (nx0 >= 0 && nx0 < msize) {
        dp1[nx0] = 1;
    }

    for (ll i = 1; i < n; i++) {
        vector<ll> ndp0(msize, inf);
        vector<ll> ndp1(msize, inf);

        for (ll x = 0; x < msize; x++) {
            ndp0[x] = min(dp0[x], dp1[x]);
        }

        for (ll x = 0; x < msize; x++) {
            if (dp0[x] != inf) {
                ll nx = x + d[i];
                if (nx >= 0 && nx < msize) {
                    if (dp0[x] + 1 < ndp1[nx]) {
                        ndp1[nx] = dp0[x] + 1;
                    }
                }
            }
        }
        for (ll x = 0; x < msize; x++) {
            if (dp1[x] != inf) {
                ll nx = x + d[i];
                if (nx >= 0 && nx < msize) {
                    if (dp1[x] < ndp1[nx]) {
                        ndp1[nx] = dp1[x];
                    }
                }
            }
        }

        dp0 = move(ndp0);
        dp1 = move(ndp1);
    }

    ll ans = inf;
    for (ll x = 0; x < msize; x++) {
        if (dp0[x] == inf && dp1[x] == inf) continue;
        long long xv = (long long)(x - f);
        if (abs(T0 - 2 * xv) <= m) {
            if (dp0[x] < ans) ans = dp0[x];
            if (dp1[x] < ans) ans = dp1[x];
        }
    }

    if (ans == inf) {
        ans = n;
    }

    cout << ans << endl;
    return 0;
}

/*
输入处理：读取骨牌数量n和目标值m，计算每个骨牌的差值d_i和初始总差T0。

初始化DP数组：dp0和dp1分别存储不在区间中和在区间中的状态，大小为100001（覆盖X的偏移范围）。

初始状态设置：第一个骨牌不翻转（X=0）或在区间中翻转（X=d[0]）。

状态转移：遍历每个骨牌，更新状态：

新dp0：从上一状态的dp0或dp1不翻转当前骨牌转移而来。

新dp1：从dp0翻转当前骨牌（操作数+1）或从dp1翻转当前骨牌（操作数不变）转移而来。

结果检查：遍历所有可能的X值，检查是否满足|T0 - 2X| ≤ m，并记录最小操作次数。

输出：满足条件的最小操作次数，若无解则输出n（最坏情况）。

此方案通过动态规划高效求解最小操作次数，时间复杂度为O(n × range_size)，其中range_size为100001，适用于给定约束。

*/